package list;

/**
 * @version 1.0
 * 功能目的描述 ：用于      约瑟夫环   ========>>>>>>>>>>>
 * @author： pang-yun
 * @date： 2021-07-21 20:54
 */

public class JosephListDemo {
    public static void main(String[] args) {

        JosephList josephList = new JosephList();
        josephList.addNode(15);
        josephList.showJosephusNode();

        System.out.println("--------------josephus-------------");
        josephList.count(1,4,5);
    }
}

//创建环形的单向链表
class JosephList {
    //创建一个first节点  当前没有编号
    private Node first = null;
    private Node current;

    //添加节点， 构建环形链表
    public void addNode(int nums) {
        //首先进行一个对输入数据的验证
        if (nums < 1) {
            System.out.println("数据有问题，无法创建1以下的环形链表");
        }

        //创建辅助指针current
        Node current = null;

        //使用for循环来创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号来创建节点，
            Node node = new Node(i);

            //第一个创建时构成一个环
            if (i == 1) {
                first = node;
                first.next = first;
                current = first;  //first不能动，只能用current辅助指针实现
            } else {
                //current 先指向新的节点
                current.next = node;

                //node的下一个指向 first  形成闭环
                node.next = first;

                //将current  移到下一个
                current = node;
            }
        }
    }

    //遍历环形链表
    public  void showJosephusNode(){

        //判断链表是否为空
        if (first==null){
            System.out.println("空链表");
            return;
        }
        Node current = first;
        while (true){
            System.out.printf("Josephus编号： %d\n",current.number);
            if (current.next==first){  //当current.next==first时，说明已经遍历完毕了
                break;
            }
            current=current.next;  //指针后移
        }
    }

    //根据输入  确定出圈顺序

    /**
     *
     * @param startNum  从第几个开始
     * @param countNum   数几次
     * @param nums      总共有多少个
     */
    public void count(int startNum , int countNum , int nums){
        if (first==null || startNum<1 || startNum>nums){
            System.out.println("输入的参数有误，请重新输入");
        }

        //创建 辅助指针， 帮助完成 数到第几个  , 让helper 指向最后一个节点
        Node helper = first;
        while (true){
            if (helper.next==first){break;}
            helper=helper.next;
        }

        //不一定从第一个开始数，可能是从第  startNum  个开始数，在此之前吗，首先移动 startNum -1
        for (int j=0; j< startNum -1 ;j++){
            first= first.next;
            helper=helper.next;
        }

        //开始数，每countNum 个出圈    注意：这里是 循环操作，只有到只剩下一个时结束
        while (true){
            //说明只有一个  出圈
            if (helper==first){break;}

            //让 first  helper  同时移动 countNum  -1  出圈
            for (int k=1; k<countNum; k++){
                first=first.next;
                helper=helper.next;
            }

            //这时候 first 已经指向了 要出圈的node， helper 指向 node的前一个
            System.out.printf("编号为： %d  的node出圈\n",first.number);

            //找到node后有两个动作， first 指向节点已经出去  需要指向下一个重新开始  helper还是前一个  需要用它将链表连接起来！
            first=first.next;
            helper.next =first;
        }
        System.out.printf("剩下的最后一个node编号： %d\n",helper.number);
    }



}

//单个节点
class Node {
    public int number;
    public Node next;

    public Node(int number) {
        this.number = number;
    }

}
